﻿#include <iostream>
#include "../Util/util.h"

#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)

typedef struct
{
	int minNum;
	int maxNum;
	bool used;
	char padding[3];
}BucketForMaxGap;

static int bucketIndex(const int number, const int minValue, const int maxValue, const size_t numbersSize)
{
	float a = number - minValue;
	float b = maxValue - minValue;
	return (int)(a / b * numbersSize);
}

static int maxGap(const int* numbers, const size_t numbersSize)
{
	int minValue = numbers[0];
	int maxValue = numbers[numbersSize - 1];
	if (minValue == maxValue) return 0;

	BucketForMaxGap* buckets = (BucketForMaxGap*)malloc((numbersSize + 1) * sizeof(BucketForMaxGap));
	memset(buckets, 0, (numbersSize + 1) * sizeof(BucketForMaxGap));

	int index;
	BucketForMaxGap* curBucket;
	int cur;
	for (int i = 0; i < numbersSize; i++)
	{
		cur = numbers[i];
		index = bucketIndex(cur, minValue, maxValue, numbersSize);
		curBucket = buckets + index;
		if (!curBucket->used)
		{
			curBucket->maxNum = cur;
			curBucket->minNum = cur;
			curBucket->used = true;
		}
		else
		{
			curBucket->maxNum = MAX(curBucket->maxNum, cur);
			curBucket->minNum = MIN(curBucket->minNum, cur);
		}
	}

	BucketForMaxGap* lastBucket = buckets;
	int maxOffset = 0;
	int offset;
	for (int i = 1; i < numbersSize + 1; i++)
	{
		curBucket = buckets + i;
		if (curBucket->used)
		{
			offset = curBucket->minNum - lastBucket->maxNum;
			maxOffset = MAX(maxOffset, offset);
			lastBucket = curBucket;
		}
	}

	free(buckets);
	return maxOffset;
}

/**
 * 给定一个数组，求如果排序之后，相邻两数的最大差值。要求时间复杂度O(N), 且要求不能用基于比较的排序方法(快速排序，堆排序，归并排序...)。
 * 
 * 思路：
 * 使用桶排序思路，为arr建(size+1)个桶，把所有的数字按照((arrMax-arrMin)/size)平均分成size个区间，然后依次把各个数字塞到对应的区间中，每个区间自成一个桶。最大差值肯定是一个桶的最小值 减 它左侧的有数字的桶的最大值。
 */
int main_maxGap()
{
	auto numbersSize = 15;
	int* numbers;
	generateSomeRandomNumbers(10, 1000, &numbers, numbersSize, true);
	for (int i = 0; i < numbersSize; i++)
	{
		printf("numbers[%d]=%d\n", i, numbers[i]);
	}

	int maxOffset = maxGap(numbers, numbersSize);
	printf("%d\n", maxOffset);
	free(numbers);

	return 0;
}